package com.leetcode.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/23 22:07
 */
public class PartitionLabels_763 {

    public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        // 先遍历一遍更新每个字母的最后位置
        for (int i = 0; i < S.length(); ++i)
            last[S.charAt(i) - 'a'] = i;
        int j = 0, anchor = 0;
        List<Integer> ans = new ArrayList<>();
        // 计算当前游标的最终位置和当前最大位置
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            // 如果两者相等，证明这个区间划分了出来
            if (i == j) {
                ans.add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return ans;
    }

    public List<Integer> partitionLabels2(String S) {
        int pos = 0, jump = 0, cut = -1;
        List<Integer> list = new ArrayList<>();
        while (pos < S.length()) {
            char last = S.charAt(jump);
            jump = S.lastIndexOf(last);
            char cur = S.charAt(pos);
            if (S.lastIndexOf(cur) <= jump) {
                pos++;
            } else if (pos < jump) {
                jump = pos;
            } else{
                list.add(jump - cut);
                // 记录断点位置
                cut = jump;
                jump = pos;
            }
        }
        list.add(S.length() - 1 - cut);
        return list;
    }

}
